class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        # 枚举第一个数和第二个数的所有可能分割方式
        for i in range(1, n):
            for j in range(i + 1, n):
                num1_str = num[:i]
                num2_str = num[i:j]
                
                # 检查前导零
                if (len(num1_str) > 1 and num1_str[0] == '0') or (len(num2_str) > 1 and num2_str[0] == '0'):
                    continue
                
                num1 = int(num1_str)
                num2 = int(num2_str)
                
                # 开始递归验证
                if self.dfs(num[j:], num1, num2, 2):  # 已经有2个数了
                    return True
        return False

    def dfs(self, remaining: str, prev1: int, prev2: int, count: int) -> bool:
        # 如果剩余字符串为空，且已经匹配至少3个数，则返回True
        if not remaining:
            return count >= 3
        
        # 计算下一个期望的数字
        next_num = prev1 + prev2
        next_num_str = str(next_num)
        
        # 检查剩余字符串是否以next_num_str开头
        if remaining.startswith(next_num_str):
            # 继续递归，更新prev1, prev2 和 count
            return self.dfs(remaining[len(next_num_str):], prev2, next_num, count + 1)
        else:
            return False

# 示例测试

solution = Solution()
print(solution.isAdditiveNumber("112358"))  # True
print(solution.isAdditiveNumber("199100199"))  # True
print(solution.isAdditiveNumber("0"))  # false
 